The present invention relates to a Viterbi decoder for a convolutional code that is concatenated with a block code and transmitted in frames at a rate of two or more frames per block.
In a block code, the data to be transmitted are divided into blocks of a fixed size. A redundant code is generated from the data in each block and added to the block for the purpose of error detection or correction.
A convolutional code does not divide data into blocks, but generates output data at a rate N times higher than the input data rate, each group of N output bits being generated from the most recent K input bits. (K and N are positive integers.) Convolutional codes are commonly decoded by a maximum-likelihood algorithm known as the Viterbi algorithm.
It has been found that a low error rate can be attained by first performing a block coding process, then carrying out a convolutional coding process on the block-encoded data. Such concatenated codes have successfully returned data from the outer reaches of the solar system. They are also used in terrestrial communications: for example, in digital cellular telephony.
A natural way to decode such a concatenated code is to wait for an entire block of data to be received, then apply the Viterbi decoding algorithm and block decoding process to that block. A better method is to wait, before decoding one block, until part of the next block has been received, so as to give the Viterbi algorithm more data to work with and enable it to decode the convolutional code more accurately. A problem with both of these methods, however, is that the Viterbi algorithm requires many computational steps, so if all the computations for decoding one block must be performed in one burst, It is difficult for the decoder to operate in real time.
A further problem arises when the data are transmitted in frames and each block occupies multiple frames, with no indication of the frame in which a block begins. In this case the decoder has the additional tasks of acquiring block synchronization, detecting loss of block synchronization, and reacquiring block synchronization when lost.
Block synchronization is basically acquired by looking for agreement of the block code; that is, by checking whether the redundant code in each block has the right value. Here, however, a further problem arises: the block code may agree fortuitously, even when block synchronization has been lost.